// https://leetcode.cn/problems/last-stone-weight/description/

// 算法思路总结：
// 1. 最大堆模拟石头碰撞过程
// 2. 使用优先队列自动维护石头重量顺序
// 3. 每次取出最大的两块石头，重量不同时放入剩余重量
// 4. 重复直到剩余0或1块石头
// 5. 时间复杂度：O(nlogn)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <queue>
#include <algorithm>

class Solution 
{
public:
    int lastStoneWeight(vector<int>& stones) 
    {
        int m = stones.size();
        if (m == 1) return stones[0];
        priority_queue<int> maxHeap(stones.begin(), stones.end());

        while (maxHeap.size() > 1)
        {
            int top1 = maxHeap.top();
            maxHeap.pop();

            int top2 = maxHeap.top();
            maxHeap.pop();

            if (top1 != top2)
                maxHeap.push(top1 - top2);
        }

        return maxHeap.size() == 0 ? 0 : maxHeap.top();
    }
};

int main()
{
    vector<int> v1 = {2,7,4,1,8,1}, v2 = {0, 0};
    Solution sol;

    cout << sol.lastStoneWeight(v1) << endl;
    cout << sol.lastStoneWeight(v2) << endl;

    return 0;
}
